# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/8/4 17:17 
"""
class TreeNode:
    def __init__(self,val):
        self.val=val
        self.left=None
        self.right=None


def insert(root,val):
    """
    插入子树
    Args:
        root:
        val:

    Returns:

    """
    if root is None:
        root=TreeNode(val)
    else:
        if val<root.val:
            root.left=insert(root.left,val)
        elif val>root.val:
            root.right=insert(root.right,val)
    return root

def query(root,val):
    """
    查询
    Args:
        root:
        val:

    Returns:

    """
    if root is None:
        return -1
    if root.val is val:
        return 1

    if root.val<val:
        return query(root.right,val)
    else:
        return query(root.left,val)



def findmin(root):
    """
    寻找最小值
    Args:
        root:

    Returns:

    """

    if root.left:
        return findmin(root.left)
    else:
        return root

def delnum(root,val):
    if root is None:
        return -1
    if val<root.val:
        return delnum(root.left,val)
    elif val>root.val:
        return delnum(root.right,val)
    else:
        #删除要区分左右孩子是否为空的情况
        if root.left and root.right:
            #左右子树都存在时需要找后继节点
            tmp=findmin(root.right)
            root.val=tmp.val
            root.right=delnum(root.right,val)
            #实际删除的是这个后继节点
        else:
            if root.left is None:
                root=root.right
            elif root.right is None:
                root=root.left
    return root

if __name__=="__main__":
    # 測试代码
    root = TreeNode(3);
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 4);

    # print query(root,3);
    print(query(root, 1))

    root = delnum(root, 1);
    print(query(root, 1))


